#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 单链表 
/*
    节点  ： 数据 + 下一个节点的指针 (addr)
    多个节点 一起构成的  ->

    CRUD 增删改查 
    增 ：  头插和尾插 
    删除  
    查 display search 
*/

typedef  struct Node {
    int data;
    Node* next;
}Node;

typedef struct SingleList{
    Node* head;
}SingleList;

Node* createNode(int data){
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL){
        printf("error segmentation\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

SingleList* createList(){
    SingleList* list = (SingleList*)malloc(sizeof(SingleList));
    if(list == NULL){
        printf("error segmentation\n");
        exit(1);
    }
    list->head = NULL;
    return list;
}

bool isEmpty(SingleList *l){
    return l->head == NULL;
}

void insertAtHead(SingleList* list, int data){
    Node* newNode = createNode(data);
    if(isEmpty(list)){
        list->head = newNode;
        return;
    }else{
        newNode->next = list->head;
        list -> head = newNode;
    }
}

void insertAtTail(SingleList* list,int data){
    Node* newNode = createNode(data);
    if(isEmpty(list)){
        list->head = newNode;
    }
    Node* current = list->head;
    while(current->next != NULL){
        current = current->next;
    }
    current->next = newNode;
}

void insertAtPosition(SingleList* list,int data,int position){
    Node* newNode = createNode(data);
    if(position < 0){
        printf("error position!\n");
        return;
    }
    if(position == 0){
        insertAtHead(list,data);
        return;
    }

    Node* current = list->head;
    Node* prev = NULL;
    int size = 0;// length yxz lys 
    while(current != NULL && size < position){
        size++;
        prev = current;
        current = current->next;
    }
    // size = position 
    if(current != NULL){
        prev->next = newNode;
        newNode->next = current;
    }else{
        printf("yxz 是坏人 !\n");
        return;
    }
}

void deleteNode(SingleList* list,int data){
    if(isEmpty(list)){
        printf("lys偷走了所有的元素 无法删除 \n");
        return;
    }
    if(list->head->data == data){
        Node* current = list->head;
        list->head = list->head->next;
        free(current);
        return;
    }
    Node* current = list->head;
    Node* prev = NULL;
    while(current != NULL){
        if(current->data == data){
            prev->next = current->next;
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

void display(SingleList* list){
    if(isEmpty(list)){
        printf("list is empty !\n");
        return;
    }
    Node* current = list->head;
    while(current != NULL){
        printf("%d -> ",current->data);
        current = current->next;
    }
    printf("NULL\n");
}

bool search(SingleList* l,int data){
    if(isEmpty(l)){
        return false;
    }
    Node* current = l -> head;
    while(current != NULL){
        if(current -> data == data){
            return true;
        }
        current = current->next;
    }
    return false;
}


int main(){
    SingleList *l = createList();
    insertAtHead(l,10);
    insertAtHead(l,20);
    display(l);

    insertAtTail(l,34);
    insertAtTail(l,12);
    display(l);


    insertAtPosition(l,5,2);
    display(l);
    
    deleteNode(l,20);
    display(l);
    deleteNode(l,34);
    display(l);

    printf("是否存在 lys不喜欢的 2 ：%d\n",search(l,12));
}